树|二叉树的存储结构和基本操作

二叉树的存储结构

二叉树使用链表来定义&＃xff1b;结点不存在&＃xff0c;指向NULL;

struct node{int data; // 数据域node *lchild; // 指向左子树根结点的指针node *rchild; // 指向右子树根结点的指针
}


二叉树的基本操作

1. 二叉树的建立

node *Create(int data[],int n){node *root &＃61; NULL;// 新建空根结点rootfor(int i&＃61;0; i}


2. 二叉树结点的查找&＃xff0c;修改&＃xff0c;插入&＃xff0c;与删除

使用递归来完成查找修改工作&＃xff1b;
递归式&＃xff1a;指对当前结点的左子树和右子树分别递归
递归边界&＃xff1a;当前结点为空时到达子胡同

void search(node *root, int x, int newdata){if(root &＃61;&＃61; NULL){return;}if(root->data &＃61;&＃61; x){root->data &＃61; newdata;} search(root->lchild, x, newdata);search(root->rchild, x, newdata);
}


插入

void insert(node *&root, int x){if(root &＃61;&＃61; NULL){root &＃61;&＃61; newNode(x);return;}if(由二叉树的性质&＃xff0c;x应该插在左子树){insert(root->lchild, x);}else{insert(root->rchild, x);}
}


如何判断是否要加引用呢&＃xff1f;

一般来说&＃xff0c;如果函数中需要新建结点&＃xff0c;即对二叉树的结构做出修改&＃xff0c;就需要加引用&＃xff1b;如果只是修改当前已有结点的内容&＃xff0c;或仅仅是遍历树&＃xff0c;就不需要加引用。至于判断不出来的情况&＃xff0c;不妨直接试一下加引用和不加引用的区别再来选择。

• 在新建结点之后&＃xff0c;务必令新结点的左右指针域为NULL&＃xff0c;表示这个新结点暂时没有左右子树。

代码

#include
#include
#include
using namespace std;struct node
{int data; // 数据域node *lchild; // 指向左子树根结点的指针node *rchild; // 指向右子树根结点的指针
};
node *newNode(int v)
{node *Node &＃61; new node;Node->data &＃61; v;Node->lchild &＃61; Node->rchild &＃61; NULL;return Node;
}
void insert_node(node *&root, int x)
{if (root &＃61;&＃61; NULL){root &＃61; newNode(x);return;}if (x <&＃61; root->data){insert_node(root->lchild, x);}else{insert_node(root->rchild, x);}
}node *Create(int data[], int n)
{node *root &＃61; NULL; // 新建空根结点rootfor (int i &＃61; 0; i }void printNodes(node *root)
{if (root &＃61;&＃61; NULL){return;}printf("%d ", root->data);printNodes(root->lchild);printNodes(root->rchild);return;
}
int main()
{int data[] &＃61; {10, 9, 8, 7, 6};node *root &＃61; Create(data, 5);printNodes(root);return 0;
}